package com.lw.leetcode.arr.c;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * arr
 * stack
 * 354. 俄罗斯套娃信封问题
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/17 22:36
 */
public class MaxEnvelopes {

    public static void main(String[] args) {
        MaxEnvelopes test = new MaxEnvelopes();

        // 3
//        int[][] arr = {{1,15},{7,18},{7,6},{7,100},{2,200},{17,30},{17,45},{3,5},{7,8},{3,6},{3,10},{7,20},{17,3},{17,45}};


        // 5
//        int[][] arr = {{15,8},{2,20},{2,14},{4,17},{8,19},{8,9},{5,7},{11,19},{8,11},{13,11},{2,13},{11,19},{8,11},{13,11},{2,13},{11,19},{16,1},{18,13},{14,17},{18,19}};

        // 3
//        int[][] arr = {{5,4},{6,4},{6,7},{2,3}};

        // 3
//        int[][] arr ={{3,5},{7,8},{3,6},{3,10},{7,20},{17,3},{17,45}};

        // 6
//        int[][] arr = {{13,13},{13,13},{17,2},{13,11},{4,6},{7,7},{10,3},{1,3},{20,18},{11,2},{8,7},{1,13},{4,16},{14,16},{2,10},{1,14},{5,7},{3,12},{2,16}};

        // 7
//        int[][] arr = {{1,2},{2,3},{3,4},{3,5},{4,5},{5,5},{5,6},{6,7},{7,8}};

        // 3
//        int[][] arr = {{30,50},{12,2},{3,4},{12,15}};

        // 4
//        int[][] arr = {{4,5},{4,6},{6,7},{2,3},{1,1}};

        // 1
//        int[][] arr = {{1,1},{1,1},{1,1}} ;

        // 5
        int[][] arr = {{2, 100}, {3, 200}, {4, 300}, {5, 500}, {5, 400}, {5, 250}, {6, 370}, {6, 360}, {7, 380}};

        int i = test.maxEnvelopes(arr);
        System.out.println();
        System.out.println(i);

    }


    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
        int length = envelopes.length;
        int[] arr1 = new int[length];
        int[] arr2 = new int[length];
        arr2[0] = envelopes[0][1] + (1 << 16);
        Set<Integer> set = new HashSet<>();
        set.add(0);
        int l1 = -1;
        int l2 = 0;
        for (int i = 1; i < length; i++) {
            if (envelopes[i - 1][0] != envelopes[i][0]) {
                for (int v : set) {
                    arr1[v] = arr2[v];
                }
                set.clear();
                l1 = l2;
            }
            l2 = find(l1, arr1, arr2, envelopes[i][1], set);
        }
        return arr2[l2] >> 16;
    }

    private int find(int l, int[] arr1, int[] arr2, int t, Set<Integer> set) {
        if (l == -1) {
            l++;
            if (!set.contains(l)) {
                set.add(l);
                arr2[l] = t + (1 << 16);
            }
            return l;
        }
        int item = arr1[l] & 0XFFFF;
        if (t > item) {
            l++;
            if (!set.contains(l)) {
                set.add(l);
                arr2[l] = t + (((arr1[l - 1] >> 16) + 1) << 16);
            }
            return l;
        } else if (t == item) {
            return l;
        }
        int st = 0;
        int end = l;
        while (st < end) {
            int m = st + ((end - st) >> 1);
            item = arr1[m] & 0XFFFF;
            if (item > t) {
                end = m;
            } else {
                st = m + 1;
            }
        }
        if (st - 1 >= 0 && (arr1[st - 1] & 0XFFFF) == t) {
            return l;
        }
        if (!set.contains(st)) {
            arr2[st] = t + ((arr1[st] >> 16) << 16);
            set.add(st);
        }
        return l;
    }

}
